# Problem 3
# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?

import unittest
import math

def findLargestPrimeFactor_better(N):
    factor = 2
    while True:
        while N % factor == 0:
            N /= factor
        if factor > N:
            break
        factor += 1
    return  factor  


def isPrime(N): 
    N_root = int(math.sqrt(N))
    found_factor = False
    for i in range(2, N_root + 1):
        if N % i == 0:
            found_factor = True
            break
    return (not found_factor)


def findLargestPrimeFactor(N):
    return max(findAllPrimeFactors(N))

    
def findAllPrimeFactors(N):
    result = []
    findPrimeFactor(2, N, result)
    return result

    
def findPrimeFactor(start, N, result):
    prime = 0
    found_prime = False
    for i in range(start, N + 1):
        if isPrime(i):
            prime = i
            break
    if prime == 0: # don't find prime
        return
    first = True
    while N % prime == 0:
        N = int(N / prime)
        if first:
            result.append(prime)
            first = False
    findPrimeFactor(prime + 1, N, result)    
            

class TestP003(unittest.TestCase):
    def setUp(self):
        return

    def test_isPrime(self):
        self.assertTrue(isPrime(2))
        self.assertTrue(isPrime(3))    
        self.assertTrue(isPrime(11))
        self.assertFalse(isPrime(12))
        self.assertFalse(isPrime(4294967297))
        self.assertTrue(isPrime(6857))  
        
    def xtest_findAllPrimeFactors(self):
        self.assertEqual(findAllPrimeFactors(2), [2])
        self.assertEqual(findAllPrimeFactors(10), [2, 5])
        self.assertEqual(findAllPrimeFactors(11), [11])    
        self.assertEqual(findAllPrimeFactors(13195), [5, 7, 13, 29])
                     
    def test_findLargestPrimeFactor(self):
        self.assertEqual(findLargestPrimeFactor_better(2), 2)
        self.assertEqual(findLargestPrimeFactor_better(13195), 29)
        
    def tearDown(self):
        return

if __name__ == '__main__':  
    P003 = unittest.TestLoader().loadTestsFromTestCase(TestP003)
    unittest.TextTestRunner(verbosity=2).run(P003)
    print 'max facotor of 600851475143 is ', findLargestPrimeFactor_better(600851475143)  
 




    